package leetCode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class LeetCode_day4 {
	
	/**
	 * The typical dynamic programming example from text book.
	 * 
	 * @param n length of rod
	 * @param revenue price of each certain length
	 * @return
	 */
	public static int rodCuttingButtomUp(int n, int[] revenue){
		if(n < 1 || revenue == null || revenue.length < 1) return 0;
		
		int[] t = new int[n];
		t[0] = revenue[0];
		
		for(int i = 1 ; i < n ; i++){
			int max = 0;
			for(int j = 0 ; j <= i/2 ; j++){
				int sum = t[j]+t[i-j-1];
				if(sum > max) max = sum;//notice
			}
			if(i < revenue.length && revenue[i] > max) max = revenue[i];
			t[i] = max;
		}
		return t[n-1];
	}
	
	public static int rodCuttingTopDown(int n, final int[] revenue, int[] t){
		if(n < 1 || revenue == null || t == null || revenue.length < 1 || t.length < n) return 0;
		//base case
		if(n == 1) return revenue[0];
		//induction
		if(t[n-1] == 0){
			int max = 0;
			if(n-1 < revenue.length) max = revenue[n-1];
			for(int len = 1 ; len <= n/2 ; len++){
				if(t[len-1] == 0) t[len-1] = rodCuttingTopDown(len, revenue, t);
				if(t[n-len-1] == 0) t[n-len-1] = rodCuttingTopDown(n-len, revenue, t);
				int sum = t[len-1] + t[n-len-1];
				if(sum > max) max = sum;
			}
			return max;
		}else return t[n-1];
	}
	
	/**
	 * !The typical dynamic programming example from text book.
	 * Two matrices: pq and qr, the complex is p*q*r
	 * Given a chain of matrices, find the best parenthesizing.
	 * 
	 * The number of parenthesizations can be described by **Catalan numbers**
	 * 
	 * Logic:
	 * m[i,i] = 0;
	 * @param p all matrices dimension
	 */
	public static void matrixChainMultiplication(int[] p){
		int matNum = p.length - 1;//matrix number
		int[][] m = new int[matNum][matNum];
		int[][] s = new int[matNum][matNum];
		
		//findOtMCM(m,s,p);
		for(int i = 0 ; i < matNum-1 ; i++){
			m[i][i] = p[i];
			m[i][i+1] = p[i]*p[i+1]*p[i+2];
		}
		m[matNum-1][matNum-1] = p[matNum-1];
		
		for(int len = 3 ; len <= matNum ; len++){
			for(int start = 0 ; start < matNum-len + 1; start++){
				int end = start + len - 1;
				int cost = Integer.MAX_VALUE;
				for(int sep = start ; sep < end ; sep++){
					int sum = m[start][sep] * m[sep+1][end];
					if(cost > sum) {
						cost = sum;
						s[start][end] = sep;
					}
				}
			}
		}
		
		System.out.println(m[0][matNum-1]);
	}

	/**
	 * Given an array S of n integers, 
	 * find three integers in S such that the sum is closest to a given number, target. 
	 * Return the sum of the three integers. 
	 * You may assume that each input would have exactly one solution.
	 * @param list
	 * @param target
	 * @return
	 */
	public static int threeSumClosest(int[] list, int target){
		//check valid input
		if(list == null || list.length < 3) return Integer.MIN_VALUE;
		
		Arrays.sort(list);
		int distance = Integer.MAX_VALUE, result = 0; // to decide the distance
		//select the first number
		for(int i = 0 ; i < list.length - 2 ; i++){
			//select the other two number
			
			int newTarget = target - list[i], left = i+1, right = list.length-1;
			while(left < right){
				int sum = list[left] + list[right];
				if(sum < newTarget) left++;
				else if(sum > newTarget) right--;
				else{
					return target;
				}
			}
			
			int tempDis = Math.abs(list[left-1]+list[right]-newTarget);
			if(tempDis < distance){
				distance = tempDis;
				result = list[i] + list[left-1] + list[right];
			}
			tempDis = Math.abs(list[left] + list[right+1]-newTarget);
			if(tempDis < distance){
				distance = tempDis;
				result = list[i] + list[left] + list[right+1];
			}
		}
		
		return result;
	}
	
	
	public static void fourSum(){
		
	}
	
	/**
	 * ! A combination problem.
	 * Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
	 * For example, given n = 3, a solution set is:
	 * "((()))", "(()())", "(())()", "()(())", "()()()"
	 * 
	 * If we treat these parentheses as trees, 
	 * it can be seen as generate all possible trees including isomorphisms.
	 * But not really. Need to be discussed.
	 * 
	 * Base case: n = 1, result = "()"
	 * Induction: result(n+1) = add one pair parentheses to the result(n)
	 * @param n
	 * @return
	 */
	public static List<StringBuilder> generateParentheses(int n){
		if(n < 1) return null;
		if(n == 1){//base case
			List<StringBuilder> result = new ArrayList<StringBuilder>();
			result.add(new StringBuilder("()"));
			return result;
		}
		//induction
		List<StringBuilder> oldResult = generateParentheses(n-1);
		List<StringBuilder> result = new ArrayList<StringBuilder>();
		
		for(StringBuilder str : oldResult){
			int left = 1 , right = 0;
			while(str.charAt(right++) == ')');
			StringBuilder sb = new StringBuilder(str.toString());
			sb.insert(left, '('); 
			sb.insert(++right, ')');
			
			result.add(sb);
			
			left+=2; right+=2;
			while(str.length() > left && str.charAt(left) == '('){
				while(str.length() > right && str.charAt(right) == ')'){
					sb = new StringBuilder(str.toString());
					sb.insert(left, '('); 
					sb.insert(++right, ')');
					result.add(sb);
				}
				left+=2; right+=2;
			}
			sb = new StringBuilder(str.toString());
			sb.append("()");
			result.add(sb);
		}
		
		return result;
	}
	
	/**
	 * Just like the brain teaser horse competing.
	 * @param lists
	 * @return
	 */
	public static LinkedList<Integer> mergekSortedLists(List<LinkedList<Integer>> lists){
		if(lists == null || lists.size() == 0) return null;
		if(lists.size() == 1) return lists.iterator().next();

		LinkedList<Integer> result = new LinkedList<Integer>();
		int[] candidate = new int[lists.size()];
		Arrays.fill(candidate, Integer.MAX_VALUE);
		
		Iterator<Integer>[] iters = new Iterator[lists.size()];
		Iterator<LinkedList<Integer>> outIter = lists.iterator();
		
		int i = 0;
		while(outIter.hasNext()){
			iters[i] = outIter.next().iterator();
			if(iters[i].hasNext()){
				candidate[i] = iters[i].next();
			}
			i++;
		}
		
		int flag = 0, min = Integer.MAX_VALUE, ind = 0;
		while(flag < lists.size()){
			//get the smallest value in candidates
			min = Integer.MAX_VALUE;
			for(i = 0 ; i < candidate.length ; i++)
				if(candidate[i] < min) {
					min = candidate[i];
					ind = i;
				}
			//remove min and replace the position with new value
			result.add(min);
			if(iters[ind].hasNext())
				candidate[ind] = iters[ind].next();
			else {
				candidate[ind] = Integer.MAX_VALUE;
				flag++;
			}
		}
		return result;
	}
	
	public static void kmp(){
		
	}
	
	public static void changeArray(int[] a){
		a[0] = 9;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		/*System.out.println(rodCuttingButtomUp(9,new int[]{1,5,8,9,10,17,17,20,24,30}));
		int[] t = new int[9];
		System.out.println(rodCuttingTopDown(9,new int[]{1,5,8,9,10,17,17,20,24,30},new int[9]));
		int[] a = new int[]{1,2,3};
		changeArray(a);
		System.out.println(a[0]);
		matrixChainMultiplication(new int[]{2,3,4,5});
		System.out.println(threeSumClosest(new int[]{1,2,3,7,8,9}, 15));//*/
		/*LinkedList<Integer> list1 = new LinkedList<Integer>();
		LinkedList<Integer> list2 = new LinkedList<Integer>();
		LinkedList<Integer> list3 = new LinkedList<Integer>();
		list1.add(1); list1.add(3); list1.add(4);
		list2.add(2); list2.add(8); list2.add(14);
		list3.add(0); list3.add(3);
		
		LinkedList<LinkedList<Integer>> lists = new LinkedList<LinkedList<Integer>>();
		lists.add(list1); lists.add(list2); lists.add(list3);
		
		/*List<Integer> result = mergekSortedLists(lists);
		System.out.println();//*/
		
		StringBuilder sb = new StringBuilder("abde");
		sb.insert(2, 'c');
		List<StringBuilder> l = generateParentheses(3);
		System.out.println(sb.toString());
	}

}

/**
 * Notice:
 * StringBuilder sb = new StringBuilder("abde");
 * sb.insert(2, 'c');// sb = "abcde"
 * 
 * */
